Rankings of graphs
Identifieur interne : 002937 ( Main/Exploration ); précédent : 002936; suivant : 002938Rankings of graphs
Auteurs : H. L. Bodlaender [Pays-Bas] ; J. S. Deogun [États-Unis] ; K. Jansen [Allemagne] ; T. Kloks [Pays-Bas] ; D. Kratsch [Allemagne] ; H. Müller [Allemagne] ; Zs. Tuza [Hongrie]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1995.
Abstract
Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .
Url:
DOI: 10.1007/3-540-59071-4_56
Affiliations:
- Allemagne, Hongrie, Pays-Bas, États-Unis
- Hongrie centrale, Nebraska, Utrecht (province)
- Budapest, Utrecht
- Université d'Utrecht
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001572
- to stream Istex, to step Curation: 001460
- to stream Istex, to step Checkpoint: 001135
- to stream Main, to step Merge: 002E40
- to stream Main, to step Curation: 002937
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Rankings of graphs</title><author><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name></author><author><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name></author><author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name></author><author><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name></author><author><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name></author><author><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name></author><author><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:C10AA9E81094CD92694FF008D94185143272318F</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1007/3-540-59071-4_56</idno><idno type="url">https://api.istex.fr/document/C10AA9E81094CD92694FF008D94185143272318F/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001572</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001572</idno><idno type="wicri:Area/Istex/Curation">001460</idno><idno type="wicri:Area/Istex/Checkpoint">001135</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001135</idno><idno type="wicri:doubleKey">0302-9743:1995:Bodlaender H:rankings:of:graphs</idno><idno type="wicri:Area/Main/Merge">002E40</idno><idno type="wicri:Area/Main/Curation">002937</idno><idno type="wicri:Area/Main/Exploration">002937</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Rankings of graphs</title><author><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name><affiliation wicri:level="4"><country xml:lang="fr">Pays-Bas</country><wicri:regionArea>Department of Computer Science, Utrecht University, P.O. Box 80.089, 3508, TB Utrecht</wicri:regionArea><orgName type="university">Université d'Utrecht</orgName><placeName><settlement type="city">Utrecht</settlement><region nuts="2">Utrecht (province)</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pays-Bas</country></affiliation></author><author><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><wicri:regionArea>Department of Computer Science and Engineering, University of Nebraska-Lincoln, 68588-0115, Lincoln, NE</wicri:regionArea><placeName><region type="state">Nebraska</region></placeName></affiliation></author><author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286, Trier</wicri:regionArea><wicri:noRegion>54286, Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></affiliation></author><author><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name><affiliation wicri:level="1"><country xml:lang="fr">Pays-Bas</country><wicri:regionArea>Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O.Box 513, 5600, MB Eindhoven</wicri:regionArea><wicri:noRegion>MB Eindhoven</wicri:noRegion></affiliation></author><author><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena</wicri:regionArea><wicri:noRegion>07740, Jena</wicri:noRegion><wicri:noRegion>Jena</wicri:noRegion></affiliation></author><author><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fakultät für Mathematik und Informatik, Friedrich-Schiller-Universität, Universitätshochhaus, 07740, Jena</wicri:regionArea><wicri:noRegion>07740, Jena</wicri:noRegion><wicri:noRegion>Jena</wicri:noRegion></affiliation></author><author><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name><affiliation wicri:level="3"><country xml:lang="fr">Hongrie</country><wicri:regionArea>Computer and Automation Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111, Budapest</wicri:regionArea><placeName><settlement type="city">Budapest</settlement><region nuts="2">Hongrie centrale</region></placeName></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1995</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">C10AA9E81094CD92694FF008D94185143272318F</idno><idno type="DOI">10.1007/3-540-59071-4_56</idno><idno type="ChapterID">24</idno><idno type="ChapterID">Chap24</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶E → {1, 2, ⋯, t}) of a graph G=(V, E) is a vertex (edge) t-ranking if for any two vertices (edges) of the same color every path between them contains a vertex (edge) of larger color. The vertex ranking number χ r (G) (edge ranking number $$\chi '_r \left( G \right)$$ ) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. Among others it is shown that χ r (G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize those graphs where the vertex ranking number χ r and the chromatic number χ coincide on all induced subgraphs, show that χ r (G)=χ(G) implies χ(G)=ω(G) (largest clique size) and give a formula for $$\chi '_r \left( {K_n } \right)$$ .</div></front></TEI><affiliations><list><country><li>Allemagne</li><li>Hongrie</li><li>Pays-Bas</li><li>États-Unis</li></country><region><li>Hongrie centrale</li><li>Nebraska</li><li>Utrecht (province)</li></region><settlement><li>Budapest</li><li>Utrecht</li></settlement><orgName><li>Université d'Utrecht</li></orgName></list><tree><country name="Pays-Bas"><region name="Utrecht (province)"><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name></region><name sortKey="Bodlaender, H L" sort="Bodlaender, H L" uniqKey="Bodlaender H" first="H. L." last="Bodlaender">H. L. Bodlaender</name><name sortKey="Kloks, T" sort="Kloks, T" uniqKey="Kloks T" first="T." last="Kloks">T. Kloks</name></country><country name="États-Unis"><region name="Nebraska"><name sortKey="Deogun, J S" sort="Deogun, J S" uniqKey="Deogun J" first="J. S." last="Deogun">J. S. Deogun</name></region></country><country name="Allemagne"><noRegion><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name></noRegion><name sortKey="Kratsch, D" sort="Kratsch, D" uniqKey="Kratsch D" first="D." last="Kratsch">D. Kratsch</name><name sortKey="Muller, H" sort="Muller, H" uniqKey="Muller H" first="H." last="Müller">H. Müller</name></country><country name="Hongrie"><region name="Hongrie centrale"><name sortKey="Tuza, Zs" sort="Tuza, Zs" uniqKey="Tuza Z" first="Zs." last="Tuza">Zs. Tuza</name></region></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002937 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002937 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:C10AA9E81094CD92694FF008D94185143272318F
|texte= Rankings of graphs
}}
| This area was generated with Dilib version V0.6.31. |  |